TK!2
=v
=u
=l
#1
:n
a
:v
321654987
142536475869
79584736251
E
#2
:n
b
:v
17934
742461003907
E
#3
:n
check
:v
321654987
142536478598
590269264649
E
#4
:n
A
:v
321654987
142536475869
79584736251
0
0
0
E
#5
:n
B
:v
17934742461
3906923904
380270214035
E
#6
:n
CHECK
:v
321654987
142536475869
79584736251
8763255064
529681020962
224710981225
E
=f
#1
:n
ALIadd
:c
ALI addition
:t
Procedure
:i
a,b,c
:o
z
#2
:n
ALIsubt
:c
ALI subtraction
:t
Procedure
:i
a,b,c
:o
z
#3
:n
ALImult
:c
ALI multiplication
:t
Procedure
:i
a,b,c
:o
z
#4
:n
ALIpower
:c
ALI exponentiation
:t
Procedure
:i
a,n,b
:o
z
#5
:n
ALIsum
:c
ALI summation
:t
Procedure
:i
a,b,c
#6
:n
ALIplus
:c
ALI plus operation
:t
Procedure
:i
a,b,c
#7
:n
ALIminus
:c
ALI minus operation
:t
Procedure
:i
a,b,c
#8
:n
ALIEQ
:c
ALI "Equal To"
:t
Procedure
:i
a,b
:o
z
#9
:n
ALIGT
:c
ALI "Greater Than"
:t
Procedure
:i
a,b
:o
z
#10
:n
ALILT
:c
ALI "Less Than" 
:t
Procedure
:i
a,b
:o
z
#11
:n
RTOALI
:c
Conversion from real to ALI number
:t
Procedure
:i
x,A
:o
a
#12
:n
TOALI
:c
Conversion from real to ALI number
:t
Procedure
:i
x,A
:o
a
#13
:n
ALITOR
:c
Conversion from ALI to real number
:t
Procedure
:i
A
:o
z
#14
:n
ALIdivide
:c
ALI divide function
:t
Procedure
:i
a,b,q,r
#15
:n
ALIabs
:c
ALI absolute value
:t
Procedure
:i
a,b
#16
:n
ALIgcd
:c
Greatest common divisor of two ALI numbers
:t
Procedure
:i
a,b,c
#17
:n
listreplace
:c
Listcopy with blank first
:t
Procedure
:i
a,b
#18
:n
ALIsqrt
:c
ALI Square Root Function
:t
Procedure
:i
a,b
:o
z
#19
:n
ALIdiv
:c
ALI Division (rounded-off)
:t
Procedure
:i
a,b,c
:o
z
#20
:n
ALIdiv2
:c
ALI Division by 2
:t
Procedure
:i
a,b
:o
z
#21
:n
ALIup
:c
ALI Multiply by 10^(12*n)
:t
Procedure
:i
a,n,b
:o
z
#22
:n
ALIdown
:c
ALI Divide by 10^(12*n)
:t
Procedure
:i
a,n,b
:o
z
#1
:n
ALIadd
:z
" Notation:  a,b  names of addend lists
"            c,z  name of result list

" Supporting functions: ALIsum, ALIplus, ALIminus, ALIGT

" Description: Performs addition operation on ALI numbers.

call ALIsum(a,b,c)
z:= c
/E
E
#2
:n
ALIsubt
:z
" Notation:  a    name of minuend list
"            b    name of subtrahend list
"            c,z  name of result list

" Supporting functions: ALIsum, ALIplus, ALIminus, ALIGT

" Description: Performs subtraction operation on ALI numbers.

b[1]:= -b[1]
call ALIsum(a,b,c)
b[1]:= -b[1]
z:= c
/E
E
#3
:n
ALImult
:z
" Notation:  a,b  names of multiplicand lists
"            c,z  name of result (product) list

" Description: Performs multiplication operation on ALI numbers.

call blank(c)
sa:= sgn(a[1])
a[1]:= abs(a[1])
sb:= sgn(b[1])
b[1]:= abs(b[1])
La:= length(a)
Lb:= length(b)
for i=1 to La
   for j=1 to Lb
      (higha,lowa):= divide(a[i],1e6)
      (highb,lowb):= divide(b[j],1e6)
      (highmiddle,lowmiddle) := divide(lowa*highb+higha*lowb,1e6)
      k:= i + j

      (carry,c[k]):= divide(elt(c,k,0)+lowa*lowb+lowmiddle*1e6,1e12)

      carry:= carry + highmiddle + higha*highb
A:    k:= k-1
      (carry,c[k]):= divide(elt(c,k,0)+carry,1e12)
      if and(carry<>0,k>1) goto A
   next j
next i
if c[1]<>0 goto END
call listcopy(c,c,2)
call blank(c,length(c))
END: a[1]:= sa*a[1]
     b[1]:= sb*b[1]
     if sa*sb<0 then c[1]:= -c[1]
     z:= c
/E
E
#4
:n
ALIpower
:z
" Notation:  a    name of basis list
"            n    exponent (positive integer)
"            b,z  name of result list (power)

" Supporting function: ALImult

" Description: Performs exponentiation operation on ALI basis.

call blank(b)
call listcopy(a,b)
for i=2 to n
   call listcopy(b,'aux)
   call ALImult(a,'aux,b;b)
next i
call delete('aux)
END: z:= b
/E
E
#5
:n
ALIsum
:z
" Notation:  a,b  names of summand lists
"            c    name of result list

" Supporting functions: ALIplus, ALIminus, ALIGT

" Description: Performs summation operation on ALI numbers.

call blank(c)
if sgn(a[1])*sgn(b[1])<0 goto A
if a[1]<0 goto F
call ALIplus(a,b,c)
return

F: a[1]:= -a[1]
b[1]:= -b[1]
call ALIplus(a,b,c)
a[1]:= -a[1]
b[1]:= -b[1]
c[1]:= -c[1]
return

A: k:= 2*sgn(a[1]) + sgn(b[1])
a[1]:= abs(a[1])
b[1]:= abs(b[1])
if ALIGT(b,a) goto B
call ALIminus(a,b,c)
c[1]:= k*c[1]
goto C

B: call ALIminus(b,a,c)
c[1]:= -k*c[1]

C: if k=1 then b[1]:= -b[1]  else a[1]:= -a[1]
/E
E
#6
:n
ALIplus
:z
" Notation:  a,b  names of addend lists
"            c    name of result list

" Desription: Adds two positive ALI numbers.  Should be used only when
"             called from ALIsum.

La:= length(a)
Lb:= length(b)
if La>=Lb goto A
(a,b):= (b,a)
(La,Lb):= (Lb,La)
A: j:= Lb
carry:= 0
for i=La to 1 step -1
   c[i]:= a[i] + elt(b,j,0) + carry
   carry:= c[i]>=1e12
   if carry then c[i]:= c[i] - 1e12
   j:= j - 1
next i
if not(carry) return
for i=La to 1 step -1
   c[i+1]:= c[i]
next i
c[1]:= 1
/E
E
#7
:n
ALIminus
:z
" Notation:  a  name of minuend list
"            b  name of subtrahend list
"            c  name of result list

" Description: Subtracts a larger positive ALI number from a smaller 
"              positive ALI number.  Should be used only when called
"              from ALIsum.

call blank(c)
La:= length(a)
Lb:= length(b)
call blank('maux)
call listcopy(a,'maux)
j:= Lb
carry:= 0
for i=La to 1 step -1
   if not(carry) goto A
   'maux[i]:= 'maux[i] - 1
   carry:= 0
A: if 'maux[i]>=elt(b,j,0) goto B
   'maux[i]:= 'maux[i] + 1e12
   carry:= 1
B: c[i]:= 'maux[i] - elt(b,j,0)
   j:= j - 1
next i
for k=1 to La
   if c[k]>0 goto C
next k
C: if k=1 goto END
j:= 0
for i=k to La
   j:= j + 1
   c[j]:= c[i]
next i
for i=j+1 to La
   call blank(c,i)
next i
END: call delete('maux)
/E
E
#8
:n
ALIEQ
:z
" Notation:  a,b  names of lists with compared ALI numbers
"            z    result:  1 (true) or  0 (false)    

" Description: Compares two ALI numbers and returns  1  if they
"              are equal, and  0  if they are not.

z:= 0
La:= length(a)
if La<>length(b) return
for i=La to 1 step -1
   if a[i]<>b[i] return
next i
z:= 1
/E
E
#9
:n
ALIGT
:z
" Notation:  a,b  names of lists with compared ALI numbers
"            z    result:  1 (true) or  0 (false)    

" Description: Compares two ALI numbers and returns  1  if the 1st ALI
"              number is greater than the 2nd, or  0  if it is not.

La:= length(a)
z:= sgn(La-length(b))
if z<>0 goto END
for i=1 to La
   z:= sgn(a[i]-b[i])
   if z<>0 goto END
next i
END: z:= max(z,0)
/E
E
#10
:n
ALILT
:z
" Notation:  a,b  names of lists with compared ALI numbers
"            z    result:  1 (true) or  0 (false)    

" Description: Compares two ALI numbers and returns  1  if the 1st ALI
"              number is less than the 2nd, or  0  if it is not.

La:= length(a)
z:= sgn(length(b)-La)
if z<>0 goto END
for i=1 to La
   z:= sgn(b[i]-a[i])
   if z<>0 goto END
next i
END: z:= max(z,0)
/E
E
#11
:n
RTOALI
:z
" Notation:  x    real (TK floating point) number
"            A,a  name of target list

" Description: Conversion of real number to Arbitrary Length Integer number.

call blank(A)
if abs(x)>999999999999.5 goto conversion
A[1]:= int(x)
goto end
conversion:
(n,m):= divide(int(log(abs(x))),12)
k:= 1 + (m<12) + (m<4)
for i=1 to n+1
   if i<=k then (A[i],x):= divide(x,10^(12*(n+1-i)))  else A[i]:= 0
   if i=k then A[i]:= round(A[i]+(2*x>10^(12*(n+1-i))),10^mod(9+m,12))
next i
if x<0 then A[1]:= -A[1]
end: a:= A
/E
E
#12
:n
TOALI
:z
" Notation:  x    real (TK floating point) number
"            A,a  name of target list

" Description: Conversion of real number to Arbitrary Length Integer number.

call blank(A)
if abs(x)>999999999999.5 goto conversion
A[1]:= int(x)
goto end
conversion:
(n,m):= divide(int(log(abs(x))),12)
k:= 1 + (m<12) + (m<4)
for i=1 to n+1
   if i<=k then (A[i],x):= divide(x,10^(12*(n+1-i))) " else A[i]:= 0
   if i=k then A[i]:= round(A[i]+(2*x>10^(12*(n+1-i))),10^mod(9+m,12))
   if i>k then A[i]:= 0
next i
if x<0 then A[1]:= -A[1]
end: a:= A
/E
E
#13
:n
ALITOR
:z
" Notation:  A  list with ALI number
"            z  real number approximation of A

" Description: Conversion of Arbitrary Length Integer number to real number.

n:= length(A)
z:= A[1]
for i=2 to min(n,3)
   z:= A[i] + z*1e12
next i
z:= z*10^(12*max(0,n-3))
/E
E
#14
:n
ALIdivide
:z
" Notation:  a  name of dividend list
"            b  name of divisor list
"            q  name of quotient list (integer)
"            r  name of remainder list

" Supporting functions: ALIadd, ALIsubt, ALIsum, ALIplus, ALIminus
"                       ALIGT, ALImult, listreplace

" Description: Performs division of ALI numbers and returns lists with
"              quotient and remainder.

call blank(q)
call ALIabs(a,'auxa)
call ALIabs(b,'auxb)
call listreplace('auxa,r)
q[1]:= 0
dr:= 'auxb[1]
Lb:= length(b)
Lr:= length(r)
A:
dd:= r[1]
if dd>dr goto B
dd:= 1e12*dd
Lr:= Lr - 1
B:
call blank('aux1)
'aux1[1]:= floor(dd/(dr+(Lb>1)))
for i=2 to Lr-Lb+1
   'aux1[i]:= 0
next i
call listreplace(q,'aux2)
w:= ALIsubt('auxa,ALImult('auxb,ALIadd('aux1,'aux2,q),'aux1),r)
Lr:= length(r)
if or(Lr>Lb,and(Lr=Lb,r[1]>dr)) goto A
w:= ALIsubt(r,'auxb,'aux1)
if 'aux1[1]<0 goto C
call listreplace('aux1,r)
call listcopy(q,'aux2)
w:= ALIadd('aux2,RTOALI(1,'aux1),q)
C:
call delete('auxa)
call delete('auxb)
call delete('aux1)
call delete('aux2)
if a[1]*b[1]>=0 return
q[1]:= -q[1]
r[1]:= -r[1]
/E
E
#15
:n
ALIabs
:z
" Notation:  a  name of argument list
"            b  name of result list

call blank(b)
call listcopy(a,b)
b[1]:= abs(b[1])
/E
E
#16
:n
ALIgcd
:z
" Notation:  a,b  names of lists with arguments in ALI form
"            c    name of result list

" Supporting functions: ALIdivide, ALIadd, ALIsubt, ALIsum, ALIplus,
"                       ALIminus, ALIGT, ALImult, listreplace

" Description: Calculates the greatest common divisor of two ALI numbers.
 
call listreplace(a,'aux3)
call listreplace(b,c)
loop:
call ALIdivide('aux3,c,'aux4,'aux5)
if 'aux5[1]=0 goto END
call listreplace(c,'aux3)
call listreplace('aux5,c)
goto loop
END: call delete('aux3)
     call delete('aux4)
     call delete('aux5)
/E
E
#17
:n
listreplace
:z
call blank(b)
call listcopy(a,b)
/E
E
#18
:n
ALIsqrt
:z
" Notation:  a    name of the radicand list
"            b,z  names of the radix list

" Supporting functions: ALIup, ALIdown, ALIadd, ALIdiv, ALIdiv2, ALIdivide,
"                       listreplace

" Description: Evaluates square root of ALI number  a  through iterations
"              based on Heron's formula
"                                           a
"                     b_new  =  (b_old + ÄÄÄÄÄÄÄ) / 2
"                                         b_old

" The integer result is precise to the last digit.

call blank(b)
z:= b
La:= length(a)
Lb:= int((La+1)/2)
x:= a[1]
if La>1 then x:= x + (a[2]>.5e12)
if mod(La,2)=0 then x:= x*1e12
b[1]:= round(sqrt(x))
call ALIup(b,Lb-1,b;x)
call ALIup(a,Lb,'sqaux1;x)
loop:
call listreplace(b,'bold)
call ALIdiv('sqaux1,b,'sqaux2;x)
call ALIdown('sqaux2,Lb,'sqaux2;x)
x:= ALIdiv2(ALIadd('bold,'sqaux2,b),b)
if b[Lb]<>'bold[Lb] goto loop
if not(ALIEQ(b,'bold)) goto loop
call delete('sqaux1)
call delete('sqaux2)
call delete('bold)
/E
29
E
#19
:n
ALIdiv
:z
" Notation:  a    name of dividend list
"            b    name of divisor list
"            c,z  name of result list 

" Supporting functions: ALIdivide,ALIadd, ALIsubt, ALIsum, ALIplus,
"                       ALIminus,ALIGT, ALImult, listreplace

" Description: Performs division of ALI numbers and returns lists with
"              rounded-off quotient.

z:= c
call ALIdivide(a,b,c,'aux3)
call ALIplus('aux3,'aux3,'aux1)
if ALIGT(b,'aux1) goto clean
call listreplace(c,'aux1)
call ALIplus('aux1,RTOALI(1,'aux2),c)
clean:
call delete('aux1)
call delete('aux2)
call delete('aux3)
/E
E
#20
:n
ALIdiv2
:z
" Notation:  a    name of dividend list
"            b,z  name of result list 

" Supporting function: listreplace

" Description: Performs division of an ALI number by  2  and returns
"              rounded-off quotient

if a<>b then call listreplace(a,b)
z:= b
r:= 0 
for i=1 to length(a)
   (b[i],r):= divide(b[i]+r*1e12,2)
next i
if b[1]>0 then return
for i=1 to length(b)-1
   b[i]:= b[i+1]
next i
call blank(b,length(b))
/E
E
#21
:n
ALIup
:z
" Notation:  a    name of 1st multiplicand list
"            n    1/12 of log of 2nd multiplicand
"            b,z  name of product list

La:= length(a) 
if a<>b then call listreplace(a,b)
for i=La+1 to La+n
   b[i]:= 0
next i
z:= b
/E
E
#22
:n
ALIdown
:z
" Notation:  a    name of dividend list
"            n    1/12 of log of divisor
"            b,z  name of rounded-off quotient list



if a<>b then call listreplace(a,b)
z:= b
La:= length(a)
if La<=n then b[1]:= and(La=n,a[1]>.5e12)
if La>n then b[La-n]:= b[La-n] + (b[La-n+1]>.5e12)
for i=max(1,La-n)+1 to La
   call blank(b,i)
next i
/E
E
=r
#1
:r
" ***  Square root of Arbitrary Length Integer numbers ***
:s
C
#3
:r
" This model presents the function  ALIsqrt  for evalation of the square root
:s
C
#4
:r
" of an ALI number, and a few related ALI functions (ALIdiv, ALIdiv2, ALIup 
:s
C
#5
:r
" and ALIdown - see appropriate Function Subsheets for their definitions).
:s
C
#7
:r
" ALIsqrt  may be used for evaluation of the square root of any argument,
:s
C
#8
:r
" integer or fractional, to any number of significant digits.  Depending on
:s
C
#9
:r
" required precision, the argument must be premultiplied by 10^(12*n) by
:s
C
#10
:r
" using the function  ALIup  with the appropriate  n .
:s
C
#12
:r
" Here is an example, complemented by an additional rule that evaluates the
:s
C
#13
:r
" square (list  check ) of the square root (list  b ) of the original
:s
C
#14
:r
" argument (list  a ):
:s
C
#16
:r
'b = ALIsqrt('a,'b)
:s
C
#17
:r
'check = ALImult('b,'b,'check)
:s
C
#19
:r
" Table  abc  shows the results.  Although the result is accurate up to its
:s
C
#20
:r
" last digit, only about half the value of  check  is the same as the  
:s
C
#21
:r
" value of the original argument  a .
:s
C
#23
:r
" The accuracy of the result may be improved by premultiplying the argument:
:s
C
#25
:r
'B = ALIsqrt(ALIup('a,3,'A),'B)
#26
:r
'CHECK = ALImult('B,'B,'CHECK)
#28
:r
" The results are in table ABC.  The first three elements of the lists  A 
:s
C
#29
:r
" and  CHECK  are identical.  At the same time all digits of the list  B  are
:s
C
#30
:r
" correct by virtue of the  ALIsqrt  algorithm.  It means that the ALI number
:s
C
#31
:r
" B  now truly represents the square root of the original 3-element ALI 
:s
C
#32
:r
" number  a  from table  abc .  When we premultiplied  a  by 10^36 (turning
:s
C
#33
:r
" it to  A ) we in fact doubled the precision, improving it by 18 digits.
:s
C
#34
:r
" Thus the ALI number  B  may be interpreted as the square root of the
:s
C
#35
:r
" original ALI number  a  with 18 decimal places, i.e.
:s
C
#36
:r
"  _________________________________
:s
C
#37
:r
" û321654987142536475869079584736251 ÷ 17934742461003906.923904380270214035
:s
C
#39
:r
" Note: The solution may take quite a while on slower systems, especially if
:s
C
#40
:r
"       you set the 'Display of Intermediate Values' field in the Global
:s
C
#41
:r
"       Sheet to Yes in order to watch the solution process in the inter-
:s
C
#42
:r
"       active table.
:s
C
=p
=t
#1
:n
abc
:s
Screen
:v
Vertical
:f
1
:r
""
:c
""
:t
""
:u
#1
:l
check
:w
17
:h
""
#2
:l
a
:w
17
:h
""
#3
:l
b
:w
17
:h
""
#4
:l
sqaux2
:w
17
:h
""
#5
:l
aux1
:w
17
:h
""
#6
:l
aux2
:w
17
:h
""
E
#2
:n
ABC
:s
Screen
:v
Vertical
:f
1
:r
""
:c
""
:t
""
:u
#1
:l
CHECK
:w
17
:h
""
#2
:l
A
:w
17
:h
""
#3
:l
B
:w
17
:h
""
E
=n
#1
:n
alint
:d
15
:f

:^
Decimal
:e
"."
:m
","
:p
None
:j
Right
:s
- Only
:q
0
:x
0
:l
""
:t
""
:v
"0"
=g
#1
:c
.000001
:i
10
:v
Yes
:g
alint
:l
60
:f
66
:m
0
:w
80
:b
Yes
:a
Yes
:r
Yes
:h
No
:t
1
:n
Yes
:d
LPT1
%Tr,f,0,1,0,1,0
